package com.gwcloud.leetcode.tags.backtrace;

/** 
* @ClassName   : Leetcode037 
* @author      : ganwei 
* @date        : 2020年5月6日 
* @Description : 37. 解数独 
* 这题有点意思，解起来费点劲
*/
public class Leetcode0037 {
	boolean[][] row = new boolean[9][10];
	boolean[][] col = new boolean[9][10];
	boolean[][] block = new boolean[9][10];
	
	public boolean couldPlace(int d, int i, int j) {
		int idx = (i / 3 ) * 3 + (j / 3);
		return !(row[i][d] || col[j][d] || block[idx][d]);
	}
	
	public void placeNumber(int d, int i, int j,char[][] board) {
		int idx = (i / 3 ) * 3 + (j / 3);
		row[i][d] = true;
		col[j][d] = true;
		block[idx][d] = true;
		board[i][j] = (char)(d + '0');
    }

	public void removeNumber(int d, int i, int j,char[][] board) {

		int idx = (i / 3 ) * 3 + (j / 3);
		row[i][d] = false;
		col[j][d] = false;
		block[idx][d] = false;
		board[i][j] = '.';
	}

	
	
	/**
	 * -解题思路，回溯算法
	 */
    public void solveSudoku(char[][] board) {
        backtrack(board,0);
        for(int i = 0; i < 9; i++){
        	for(int j = 0; j < 9; j++){
        		System.out.print(board[i][j]);
        	}
        	System.out.println();
        }
    }
    
    /**
     * -回溯主题
     */
    public boolean backtrack(char[][] board, int num){
    	
		int row = num / 9;
		int col = num % 9;
		
    	if(num == 81){
    		return true;
    	}
		if(board[row][col] != '.'){
			return backtrack(board,num+1);
		}
    	//System.out.println(num);
    	for(char ch = '1'; ch <= '9'; ch++){
    		if(!isValid(board,row,col,ch)) {
    			continue;
    		}
    		
    		//尝试
    		board[row][col] = ch;
    		if(backtrack(board, num + 1)) {
    			return true;
    		}
    		//回溯
    		board[row][col] = '.';
    		
    	}
    	return false;
    }
    	
    // 判断 board[i][j] 是否可以填入 n
    boolean isValid(char[][] board, int r, int c, char n) {
    	for (int i = 0; i < 9; i++) {
    		// 判断行是否存在重复
            if (board[r][i] == n) return false;
            // 判断列是否存在重复
            if (board[i][c] == n) return false;
            // 判断 3 x 3 方框是否存在重复
            if (board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n)
                return false;
        }
        return true;
    }

    
    
    
    /**
     * -判断数独是否为有效数独
     */
    public boolean isValidSudoku(char[][] board) {
    	boolean[][] row = new boolean[9][9];
    	boolean[][] col = new boolean[9][9];
    	boolean[][] block = new boolean[9][9];
    	
    	for(int i = 0; i < 9; i++){
    		for(int j = 0; j < 9; j++){
    			if(board[i][j] != '.'){
    				int num = board[i][j]-'1';
    				int blockIndex = (i/3)*3 + j/3;
    				if(row[i][num] || col[j][num] || block[blockIndex][num]){
    					return false;
    				}else{
    					row[i][num] = true;
    					col[j][num] = true;
    					block[blockIndex][num] = true;
    				}
    			}
    		}
    	}
    	
    	return true;
    }
    
    
    /**
     * -主函数
     */
    public static void main(String[] args) {

    	char[][] board = {
    			{'.','.','.','.','.','7','.','.','9'},
    			{'.','4','.','.','8','1','2','.','.'},
    			{'.','.','.','9','.','.','.','1','.'},
    			{'.','.','5','3','.','.','.','7','2'},
    			{'2','9','3','.','.','.','.','5','.'},
    			{'.','.','.','.','.','5','3','.','.'},
    			{'8','.','.','.','2','3','.','.','.'},
    			{'7','.','.','.','5','.','.','4','.'},
    			{'5','3','1','.','7','.','.','.','.'}
    			};
    	Leetcode0037 l037 = new Leetcode0037();
    	l037.solveSudoku(board);
    }
}
